Search results for "Asymptotic computational complexity"

showing 4 items of 4 documents

An Introduction to Computational Complexity

2016

This chapter is not strictly about algebra. However, this chapter offers a set of mathematical and computational instruments that will allow us to introduce several concepts in the following chapters. Moreover, the contents of this chapter are related to algebra as they are ancillary concepts that help (and in some cases allow) the understanding of algebra.

Set (abstract data type)symbols.namesakeTheoretical computer scienceComputational complexity theoryComputer scienceAsymptotic computational complexityWorst-case complexitysymbolsComputational problemAlgebra over a fieldComputational resourceHuffman coding
researchProduct

On Physical Problems that are Slightly More Difficult than QMA

2013

We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).

Discrete mathematicsFOS: Computer and information sciencesQuantum PhysicsTheoretical computer scienceCompleteNP-easyFOS: Physical sciences0102 computer and information sciencesComputer Science::Computational ComplexityComputational Complexity (cs.CC)01 natural sciencesPHStructural complexity theoryComputer Science - Computational Complexity010201 computation theory & mathematics0103 physical sciencesAsymptotic computational complexityComplexity classF.1.2Low010306 general physicsQuantum Physics (quant-ph)Quantum complexity theoryMathematics2014 IEEE 29th Conference on Computational Complexity (CCC)
researchProduct

Algorithmic Information Theory and Computational Complexity

2013

We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…

Discrete mathematicsAverage-case complexityAlgorithmic information theoryTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESKolmogorov complexityDescriptive complexity theoryComputational physicsStructural complexity theoryTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonAsymptotic computational complexityComputer Science::Formal Languages and Automata TheoryComputational number theoryMathematics
researchProduct

Non-intersecting Complexity

2006

A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.

PHCombinatoricsAverage-case complexityStructural complexity theoryAsymptotic computational complexityWorst-case complexityComplexity classDescriptive complexity theoryQuantum complexity theoryMathematics
researchProduct